//
// Created by Administrator on 2021/11/16.
//
/*插入排序
 * 算法思想︰每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。*/
#include <cstdlib>

//直接插入排序
void InsertSort(int A[], int n) {
    int i, j, temp;
    for (i = 1; i < n; i++) {
        //将各元素插入已排好序的序列中
        if (A[i] < A[i - 1]) {
            //若A[i]关键字小于前驱
            temp = A[i];//用temp暂存A[i]
            for (j = i - 1; j >= 0 && A[j] > temp; --j) {
                //检查所有前面已排好序的元素
                A[j + 1] = A[j];//所有大于temp的元素都向后挪位
            }
            A[j + 1] = temp;//复制到插入位置
        }
    }
}

//直接插入排序（带哨兵)
void InsertSort_with_Sentinel(int A[], int n) {
    int i, j;
    for (i = 2; i <= n; i++) {
        //依次将A[2]~A[n]插入到前面已排序序列
        if (A[i] < A[i - 1]) {
            //若A[i]关键码小于其前驱，将A[i]插入有序表
            A[0] = A[i];//复制为哨兵，A[0]不存放元素
            for (j = i - 1; A[0] < A[j]; --j) {
                //从后往前查找待插入位置
                A[j + 1] = A[j];//向后挪位
            }
            A[j + 1] = A[0];//复制到插入位置
        }
    }
}

//折半插入排序
void InsertSort_HalfPrice(int A[], int n) {
    int i, j, low, high, mid;
    for (i = 2; i <= n; i++) {
        //依次将A[2]~A[n]插入前面的已排序序歹
        A[0] = A[i];//将A[i]暂存到A[0]
        low = 1;
        high = i - 1;//设置折半查找的范围
        while (low <= high) {
            //折半查找(默认递增有序)
            mid = (low + high) / 2;//取中间点
            if (A[mid] > A[0]) {
                high = mid - 1;//查找左半子表else
            }
            low = mid + 1;//查找右半子表
        }
        for (j = i - 1; j >= high + 1; --j) {
            A[j + 1] = A[j];//统一后移元素，空出插入位置
        }
        A[high + 1] = A[0];//插入操作
    }
}
/*希尔排序︰
 * 先将待排序表分割成若干形如L[i,i + d,i + 2d...., i + kd]的“特殊”子表，
 * 对各个子表分别进行直接插入排序。
 * 缩小增量d，
 * 重复上述过程，直到d=1为止。
 *
 * 只适用于：顺序表；不适用于链表*/
//希尔排序
void Hill_Sort(int A[], int n) {
    int d, i, j;
    //A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
    for (d = n / 2; d >= 1; d = d / 2) {
        //步长变化
        for (i = d + 1; i <= n; ++i) {
            if (A[i] < A[i - d]) {
                // 需将A[i]插入有序增量子表
                A[0] = A[i];//暂存在A[0]
                for (j = i - d; j > 0 && A[0] < A[j]; j -= d) {
                    A[j + d] = A[j];//记录后移，查找插入的位置
                }
                A[j + d] = A[0];//插入
            }//if
        }
    }
}
/* 比较排序
 * 基于“交换”的排序︰根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置*/

/*“一趟”冒泡排序：
 * 从后往前(或从前往后)两两比较相邻元素的值，若为逆序（即A[i-1]>A[i])，则交换它们，直到序列比较完。*/
//交换
void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

//冒泡排序
void Bubble_Sort(int A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool flag = false;//表示本趟冒泡是否发生交换的标志
        for (int j = n - 1; j > i; j--) {
            //一趟冒泡过程
            if (A[j - 1] > A[j]) {
                //若为逆序
                swap(A[j - 1], A[j]); //交换
                flag = true;//修改交换的标志
            }
        }
        if (!flag) {
            //!flag==true即为flag==false
            return;//本趟遍历后没有发生交换，说明表已经有序
        }
    }
}

/*算法思想∶在待排序表L[1...n]中任取一个元素pivot作为枢轴（或基准，通常取首元素)，
 * 通过一趟排序将待排序表划分为独立的两部分L[1...k-1]和LIk+1...n]，
 * 使得L[1..k-1]中的所有元素小于pivot，Llk+1..n]中的所有元素大于等于pivot，
 * 则pivot放在了其最终位置L(k)上，这个过程称为一次“划分”。
 * 然后分别递归地对两个子表重复上述过程，
 * 直至每部分内只有一个元素或空为止，
 * 即所有元素放在了其最终位置上。*/

//用第一个元素将待排序序列划分成左右两个部分
int Partition(int A[], int low, int high) {
    int pivot = A[low];//第一个元素作为枢轴
    while (low < high) {
        //用low、high搜索枢轴的最终位置
        while (low < high && A[high] >= pivot) {
            --high;
        }
        A[low] = A[high];//比枢轴小的元素移动到左端
        while (low < high && A[low] <= pivot) {
            ++low;
        }
        A[high] = A[low];//比枢轴大的元素移动到右端
    }
    A[low] = pivot;//枢轴元素存放到最终位置
    return low;//返回存放枢轴的最终位置
}

//快速排序
void QuickSort(int A[], int low, int high) {
    if (low < high) {
        // 递归跳出的条件
        int Pivot_position = Partition(A, low, high); //划分
        QuickSort(A, low, Pivot_position - 1); //划分左子表
        QuickSort(A, Pivot_position + 1, high); //划分右子表
    }
}

//简单选择排序
void SelectSort(int A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        //一共进行n-1趟
        int min = i;//记录最小元素位置
        for (int j = i + 1; j < n; j++) {
            //在Al[..n-1]中选择最小的元素
            if (A[j] < A[min]) {
                min = j;//更新最小元素位置
            }
        }
        if (min != i) {
            swap(A[i], A[min]);//封装的swap()函数共移动元素3次
        }
    }
}


//将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len) {
    A[0] = A[k];//A[0]暂存子树的根结点
    for (int i = 2 * k; i <= len; i *= 2) {
        //沿key较大的子结点向下筛选
        if (i < len && A[i] < A[i + 1]) {
            i++;//取key较大的子结点的下标(i=更大的那个孩子)
        }
        if (A[0] >= A[i]) {
            break;//筛选结束
        } else {
            A[k] = A[i];//将A[i ]调整到双亲结点上
            k = i;//修改K值，以便继续向下筛选
        }
    }
    A[k] = A[0];//被筛选结点的值放入最终位置
}

//建立大根堆
void BuildMaxHeap(int A[], int len) {
    for (int i = len / 2; i > 0; i--) {
        HeadAdjust(A, i, len);//从后往前调整所有非终端结点
    }
}

//堆排序的完整逻辑
void HeapSort(int A[], int len) {
    BuildMaxHeap(A, len);//初始建堆
    for (int i = len; i > 1; i--) {
        //n-1趟的交换和建堆过程
        swap(A[i], A[1]);//堆顶元素和堆底元素交换
        HeadAdjust(A, 1, i - 1);//把剩余的待排序元素整理成堆
    }
}

/*归并排序*/
int n;
int *B = (int *) malloc(n * sizeof(int)); // 辅助数组B
//A[0...mid]和A [mid+..high]各自有序，将两个部分归并

void Merge(int A[], int low, int mid, int high) {
    int i, j, k;
    for (k = low; k <= high; k++) {
        B[k] = A[k];//将A中所有元素复制到B中
    }
    for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
        if (B[i] <= B[j]) {
            A[k] = B[i++];//将较小值复制到A中
        } else {
            A[k] = B[j++];
        }
    }//for
    while (i <= mid) {
        A[k++] = B[i++];
    }
    while (j <= high) {
        A[k++] = B[j++];
    }
}

void MergeSort(int A[], int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;//从中间划分
        MergeSort(A, low, mid);//对左半部分归并排序
        MergeSort(A, mid + 1, high);//对右半部分归并排序
        Merge(A, low, mid, high); //归并
    }//if
}